Masala #1075

Xotira 16 MB Vaqt 1000 ms Qiyinchiligi 47 %

#Perebor

#Dinamik dasturlash

#Depth-First Search

Bayram stoli

Bitvoy do'stlari bilan bayram uyushtirmoqchi. Ammo u do'stlari uchun to'g'ri to'rtburchak shaklidagi stol buyurtma qilmoqchi. U juda sahiy. Shuning uchun iloji boricha ko'proq mehmon o'tirishi mumkin bo'lgan stol buyurtma qilmoqchi. Bunda stol sig'imi uning perimetri bilan bir xil. Bitvoy eng ko'pi bilan necha nafar do'stini taklif qilishi mumkinligi aniqlang. Stolda o'zi ham o'tirishi kerak.

Kiruvchi ma'lumotlar:

Kirish faylida birinchi qatorda Bitvoyning uyini o'lchamlari kiritiladi. N, M\((1\le N, M \le 400)\).

Keyingi N qatorda Bitvoy uyining xaritasi M tadan belgi, bunda X -> bu joy allaqachon band, nuqta(.) -> bo'sh joyni anglatadi.

Chiquvchi ma'lumotlar:

Chiqish faylida Bitvoy nechta do'stini chaqirishi mumkin ekanligini chop eting.

Misollar

#	input.txt	output.txt
1	1 1 .	3
2	10 10 ....X..... X......... .......... .......... .......... .......... .......X.. .......... ..X....... ...X......	27

Izoh:

1-testda:

Demak eng ko'pi bilan 2x2 o'lchamli stol buyurtma qilishi mumkin.

P = 2 * (1 + 1) = 4

O'zi ham borligi uchun 4 - 1=3.

2-testda:

Demak eng ko'pi bilan 10x4 o'lchamli stol buyurtma qilishi mumkin.

P = 2 * (4 + 10) = 28

O'zi ham borligi uchun 28 - 1=27.

Telegram Facebook

Yechimini yuborish

Bu amalni bajarish uchun tizimga kiring, agar profilingiz bo'lmasa istalgan payt ro'yxatdan o'tishingiz mumkin